1. Field of the Invention
The present invention relates to a method and apparatus for generating a mask pattern data used for a high speed mask patterning by an electron beam from an original mask pattern data during a photo mask production for a semiconductor device.
2. Description of the Related Art
When transferring a mask pattern by irradiating electron beam on a photo mask substrate formed by coating an electron beam resist on film material, it is necessary to convert a designed original mask pattern data to a mask pattern data for a graphic processing apparatus. In the converting processing of the mask pattern data, various graphic signal processing is carried out such as the processing for avoiding the overlapping of patterns accepted in designing mask pattern data for preventing multiple pattern drawing and the processing of the inter-layers for generating pattern data based on a mask pattern data of other layers.
In order to perform the graphic signal processing effectively at a high speed, a variety of methods are proposed. One of them is known as a plane scanning method.
The plane scanning method will be explained with reference to FIGS. 6A to 6C.
When processing the pattern data as shown in FIG. 6A, a line called a scanning line in parallel with an X axis or a Y axis (X axis in FIG. 6B) is moved along vertexes of each pattern as shown in FIG. 6B. Then any desired graphic signal processing is performed to a figure between a current scanning line and a previous scanning line.
When the scanning line is applied in the same way as in FIG. 6B to the pattern data shown in FIG. 6A, the processing such as the judging and eliminating of overlap is performed for each region divided by the scanning lines while moving the scanning line. As a result, the mask pattern data for the graphic processing as shown in FIG. 6C is generated which is expressed as a group of rectangles without overlapping and a group of trapezoids.
In the processing using the plane scanning method, the processing is carried out by a unit of a line segment divided by each scanning line. Accordingly, each line segment is sorted with respect to the X axis to be controlled and it is necessary to delete or insert a line segment every time the desired graphic signal processing is carried out by moving the scanning line.
In order to effectively control the line segments and to easily delete or insert them, the data for the line segments are usually stored in a balanced two branch tree structure of evenly divided into two as shown in FIGS. 7A and 7B.
Recently, patterns of semiconductor devices have become precise and complex so that the processing time needed for converting the designed mask pattern data into the mask pattern data for the graphic processing rendered with electron beam has become enormous, and therefore high speed processing is desired.
In the converting process as explained above, majority of the time in preparing data for the graphic processing apparatuses is spent for the graphic signal processing such as the processing for eliminating overlap of patterns to prevent multiple pattern drawing and the processing of inter-layers for generating the pattern data based on the mask pattern data of other layers. Among the processing, the accessing of the above line segment data having a balanced two branch tree structure of evenly divided into two, that is, the processing for inserting, deleting and searching of the above line segment is the most time consuming process.
In the data having the tree structure of evenly divided into two, as shown in FIGS. 7A and 7B, when assuming a number of stored data as n, a depth of the data structure of evenly divided into two becomes logarithm n. Accordingly, when accessing the data, an access is made to the deepest point at the worst case so that it becomes necessary to compare logarithm n data elements making the time for accessing long. This long accessing time affects the whole converting processing of the mask pattern data for the graphic processing rendered with electron beam as explained above.